/*
 *  GEOrderedTree.h
 *  GETestRender
 *
 *  Created by Quoc Dung Chu on 23/07/11.
 *  Copyright 2011 Paris 6. All rights reserved.
 *
 */

#ifndef GE_ORDERED_TREE_H
#define GE_ORDERED_TREE_H

namespace game_engine {
	namespace core {
#pragma mark -
#pragma mark STNode

		template<class T> class CTree;
		template<class T>
		class CTNode {
            
            protected:
            CTNode<T>*  _parent;
            //CTree<T>*   _smallestTree;// the smallest tree that contains this node
			CTree<T>*	_left;
			CTree<T>*	_right;
			T			_element;
            
            public:
			CTNode(const T& element):_element(element),_left(0),_right(0),_parent(0){};
            
            virtual ~CTNode(){}
            //-------------------------------------------------------------------------
            //METHODS
            public:
            CTNode<T>* leftNode()
            {
                if (!this->_left) return 0;
                return this->_left->root();
            }
            //-------------------------------------------------------------------------
            CTNode<T>* rightNode()
            {
                if (!this->_right) return 0;
                return this->_right->root();
            }
            //-------------------------------------------------------------------------

            bool isLeftOfParent()
            //pre condition: this node have a parent
            {
                if (!this->_parent) 
                {
                    //raise exception here
                }
                return this->_parent->left() && this->_parent->left()->root() == this;
            }
            //-------------------------------------------------------------------------
            bool isRightOfParent()
            //pre condition: this node have a parent
            {
                if (!this->_parent) 
                {
                    //raise exception here
                }
                return this->_parent->right() && this->_parent->right()->root() == this;
            }
            //-------------------------------------------------------------------------
            void switchElement (CTNode<T> * node )
            {
                if (!node) return ;
                T tempoElement = node->element();
                node->element(this->element());
                this->element(tempoElement);
//                if (node == _parent ) //if my parent is node
//                {
//                    //then I become node's parent
//                    CTNode<T>* tempoNode = node->parent();
//                    node->parent(this);
//                    this->_parent = tempoNode;
//                }
//                else if ( node->parent() == this ) //else if i am node's parent                
//                {
//                    //then node becomes my parent
//                    CTNode<T>* tempoNode = this->_parent;
//                    this->_parent = node;
//                    node->parent(tempoNode);
//                }
//                
////                CTree<T>* tempoTree = node->smallestTree();
////                node->smallestTree(this->smallestTree());
////                this->smallestTree(tempoTree);
//                
//                CTree<T>* tempoTree = node->left();
//                node->left(this->left());
//                this->left(tempoTree);
//                
//                tempoTree = node->right();
//                node->right(this->right());
//                this->right(tempoTree);
            }
            //-------------------------------------------------------------------------
            void switchUpUntillFindNode( CTNode<T>* node)
            {
                CTNode<T>* itNode = this;
                while (itNode && itNode->parent() && itNode->parent() != node) {
                    this->switchElement(itNode->parent());
                    itNode = itNode->parent();
                }
            }
            //-------------------------------------------------------------------------
			//PROPRIETIES
            public:
            CTNode<T>*  parent() { return _parent; }
            void        parent ( CTNode<T> * node ) { _parent = node; }
            //----------------------------
//            CTree<T>*   smallestTree() { return _smallestTree; }
//            void        smallestTree ( CTree<T>* tree ) { _smallestTree = tree; }
            //----------------------------
            CTree<T>*   left() { return _left; }
            void        left ( CTree<T>* tree ) { _left = tree; }
            //----------------------------
            CTree<T>*   right() { return _right; }
            void        right ( CTree<T>* tree ) { _right = tree; }
            //----------------------------
            T           element() { return _element; }
            void        element ( T e ) { _element = e; }
                        
            
		};
#pragma mark -
#pragma mark General functions
//        template<class T> 
//        inline bool isParent( STNode<T> * parent , STNode<T> * child )
//        {
//            if (!parent) return false;
//            if (parent->Left && parent->Left == 
//                
//        }
        
//        template<class T> 
//        inline void switchNode ( STNode<T> * node1, STNode<T> node2 )
//        {
//            if ( node1 == node2->Parent )
//            {
//                
//            }
//        }
        
        //----------------------------
        template<class T> 
        inline void leftRotate(CTNode<T> * root)
        {
            //CTree<T> * rightTree = root->right();
            
        }
        //----------------------------
        template<class T> 
        inline void rightRotate(CTNode<T> * node)
        {
            
        }        
        
        
#pragma mark -
#pragma mark CTree

		template<class T>
		class CTree  {
			
		protected:
			CTNode<T>*		_root;
			int				_size;
		public:
			CTree():_root(0),_size(0){};
			CTree(const T& element):_root(new CTNode<T>(element)),_size(1) { /*_root->smallestTree(this);*/ };
			CTree(CTNode<T>* node):_root(node),_size(1){/* if (node) _root->smallestTree(this); */};
			
			virtual ~CTree()
			{
				//NSLog(@"delete CTree");
				clear();
			};
			//-------------------------------------------------------------------------
			//METHODS
		protected:
			void clear()
			{
				if (!_root) return;
				
				if (_root->left()) _root->left()->clear();
				if (_root->right()) _root->right()->clear();
				
				delete _root;
			}
       
			//-------------------------------------------------------------------------
			//PROPRIETIES
		public:
			CTNode<T>* root() { return _root; }
			
			int size() { return _size; }
		};
#pragma mark -
#pragma mark COrderedTree
		template< class T>
		class COrderedTree : public CTree<T> 
		{
		private:
			CTNode<T>* _last;
			
		public:
			COrderedTree():CTree<T>(){};
			COrderedTree(const T& element):CTree<T>(element) { };
			COrderedTree(CTNode<T>* node):CTree<T>(node) { };
			
			virtual ~COrderedTree()
			{
				//NSLog(@"delete COrderedTree");
			};
			//-------------------------------------------------------------------------
		private:
            //add a node in the tree : size(left branch)-size(right branch) <= 1
			void _addEqually(CTNode<T>* node)
			{
				//STNode<T>* node = new STNode<T>();
				++this->_size;
				
				if(!this->_root)
				{
					this->_root = node;
                    //node->smallestTree ( this );
					return;
				}
				
				if (!this->_root->left())
				{
					COrderedTree<T>* leftTree = new COrderedTree<T>(node);
                    this->_root->left (leftTree);
                    node->parent(this->_root);
                    
                    return;
				}
				
				if (!this->_root->right())
				{
					COrderedTree<T>* rightTree = new COrderedTree<T>(node);
					this->_root->right (rightTree);
                    node->parent(this->_root);
					return;
				
				}
				
				if (this->_root->left()->size() <= this->_root->right()->size()) 
				{
					((COrderedTree<T>*)this->_root->left())->_addEqually(node);
				}
				else 
				{
					((COrderedTree<T>*)this->_root->right())->_addEqually(node);
				}

			}
            //-------------------------------------------------------------------------
            bool _isValidOnLeft( CTNode<T>* node)
            {
                return ( !node->left() || (!node->left()->root()) || (node->left()->root()->element() <= node->element()));
            }
            //-------------------------------------------------------------------------
            bool _isValidOnRight( CTNode<T>* node)
            {
                return ( !node->right() || (!node->right()->root()) || (node->right()->root()->element() >= node->element()));

            }
            //-------------------------------------------------------------------------

            bool _isValid ( CTNode<T>* node)
            {
                return this->_isValidOnLeft(node) && this->_isValidOnRight(node);
            }
            
            //-------------------------------------------------------------------------
            
            CTNode<T>* _minChildNodeOfNode(CTNode<T>* node)
            {
                CTNode<T>* itNode = node;
                while (itNode)
                {
                    itNode = itNode->leftNode();
                }
                return itNode;
            }
            //-------------------------------------------------------------------------
            CTNode<T>* _maxChildNodeOfNode(CTNode<T>* node)
            {
                CTNode<T>* itNode = node;
                while (itNode)
                {
                    itNode = itNode->rightNode();
                }
                return itNode;
            }
            //-------------------------------------------------------------------------
           
                        
            bool _checkAndSwitchLeft(CTNode<T>* aNode)
            {
                CTNode<T>* node = aNode;
                if (!node || !node->leftNode() || (node->leftNode()->element() < node->element()) ) return false;
                node->switchElement(node->leftNode());
                if (node->parent()) {
                    bool checkLeft = this->_checkAndSwitchLeft(node->parent());
                    if(!checkLeft) this->_checkAndSwitchRight(node->parent());

                }
                else
                {
                    node = node->leftNode();
                    bool checkLeft = this->_checkAndSwitchLeft(node->leftNode());
                    if(!checkLeft) this->_checkAndSwitchRight(node->leftNode());
                }
                return true;
            }
            
            bool _checkAndSwitchRight(CTNode<T>* aNode)
            {
                CTNode<T>* node = aNode;

                if (!node || !node->rightNode() || (node->rightNode()->element() > node->element()) ) return false;
                node->switchElement(node->rightNode());
                
                if (node->parent()) {
                    bool checkLeft = this->_checkAndSwitchLeft(node->parent());
                    if(!checkLeft) this->_checkAndSwitchRight(node->parent());
                }
                else
                {
                    node = node->rightNode();
                    bool checkLeft = this->_checkAndSwitchLeft(node->rightNode());
                    if(!checkLeft) this->_checkAndSwitchRight(node->rightNode());
                }
                return true;
            }
            
            //-------------------------------------------------------------------------

            //FIXME : need refactoring
            //let node in correct position in his tree
            void _letNodeInCorrectPosition ( CTNode<T> * node)
            {
                if (!node) return;
                //go up
                CTNode<T>* itNode = node;
                CTNode<T>* itParentNode = node->parent();
                while (itParentNode /*&& itNode->element() <= itParentNode->element()*/) 
                {
                    if ((itNode->isLeftOfParent() && itNode->element() > itParentNode->element()) 
                        || (itNode->isRightOfParent() && itNode->element() < itParentNode->element())) 
                    {
                        //still go up
                        itNode->switchElement(itParentNode);
                        itNode = itParentNode;
                        itParentNode = itNode->parent();
                    }
                    else if ( !itParentNode->parent())
                    {
                        //satisfy the condition, so finish going up
                        break;
                    }
                    else
                    {
                        itNode->switchElement(itParentNode->parent());
                        itNode = itParentNode->parent();
                        itParentNode = itNode->parent();
                    }
                }
                
                
                //go down
                
                while (itNode) 
                {
                    bool isValidOnLeft = this->_isValidOnLeft(itNode);
                    bool isValidOnRight = this->_isValidOnRight(itNode);
                    
                    if (isValidOnRight && itNode->rightNode() && itNode->rightNode()->leftNode() && itNode->rightNode()->leftNode()->element() < itNode->element())
                    {
                        itNode->switchElement(itNode->rightNode()->leftNode());
                        itNode = itNode->rightNode()->leftNode();
                    }
                    else if (isValidOnLeft && itNode->leftNode() && itNode->leftNode()->rightNode() && itNode->leftNode()->rightNode()->element() > itNode->element())
                    {
                        itNode->switchElement(itNode->leftNode()->rightNode());
                        itNode = itNode->leftNode()->rightNode();
                    }
                    else if (!isValidOnLeft) {
                        //go down on the left
                        //itNode->switchElement(itNode->left()->root());
                        //itNode = itNode->left()->root();
                        CTNode<T>* maxNode = this->_maxChildNodeOfNode(itNode->left()->root());
                        maxNode->switchUpUntillFindNode(itNode);
                        break;
                    }
                    else if (!isValidOnRight)
                    {
                        //go down on the right
                        //itNode->switchElement(itNode->right()->root());
                        //itNode = itNode->right()->root();
                        CTNode<T>* minNode = this->_minChildNodeOfNode(itNode->right()->root());
                        minNode->switchUpUntillFindNode(itNode);
                        break;
                    }
                    else if ((isValidOnLeft && itNode->leftNode() && !itNode->leftNode()->rightNode())
                             ||(isValidOnRight && itNode->rightNode() && !itNode->rightNode()->leftNode()))
                    {
                        break;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            //-------------------------------------------------------------------------

		public:
			void add( const T& element )
			{
				CTNode<T>* node = new CTNode<T>(element);
				_addEqually(node);
                //_letNodeInCorrectPosition(node);
                if(!_checkAndSwitchLeft(node->parent()))    _checkAndSwitchRight(node->parent());
                
                
			}
			
		};
	}
}

#endif